package com.jack.leetcode.每日一题;

import java.util.HashMap;
import java.util.Map;

public class 等式方程的可满足性 {

    public static void main(String[] args) {
        String[] equations = {"a==b","b!=a"};
        System.out.println(equationsPossible(equations));
        String[] a = {"b==a","a==b"};
        System.out.println(equationsPossible(a));
        String[] b = {"a==b","b==c","a==c"};
        System.out.println(equationsPossible(b));
        String[] c = {"a==b","b!=c","c==a"};
        System.out.println(equationsPossible(c));
        String[] d = {"c==c","b==d","x!=z"};
        System.out.println(equationsPossible(d));
        String[] e = {"c==c","f!=a","f==b","b==c"};
        System.out.println(equationsPossible(e));
    }

    public static boolean equationsPossible(String[] equations) {
        int n = equations.length;
        if(n == 0){
            return true;
        }
        int[] parent = new int[26];
        for(int i = 0;i < 26;i++){
            parent[i] = i;
        }
        for(String s : equations){
            if(s.charAt(1) == '='){
                int left = s.charAt(0) - 'a';
                int right = s.charAt(3) - 'a';
                union(parent, left, right);
            }
        }
        for(String s : equations){
            if(s.charAt(1) == '!'){
                int left = s.charAt(0) - 'a';
                int right = s.charAt(3) - 'a';
                if(findParent(parent, left) == findParent(parent, right)){
                    return false;
                }
            }
        }
        return true;
    }

    private static void union(int[] parent, int left, int right){
        parent[findParent(parent,left)] = findParent(parent,right);
    }

    private static int findParent(int[] parent, int index){
        while(parent[index] != index){
            parent[index] = parent[parent[index]];
            index = parent[index];
        }
        return index;
    }
}
